package com.javabasic.algorithm.sword_of_offer;

import java.util.Random;

/**
 * @author xiongmin
 * @version 0.0.1
 * @description Created by work on 2021/10/15 9:57 下午
 * @see
 */
public class 三个数的最大乘积 {

    public int maximumProduct(int[] nums) {
        int first = Integer.MIN_VALUE, second = Integer.MIN_VALUE, three = Integer.MIN_VALUE;
        int len = nums.length;
        for (int i = 0; i < len; i++) {
            if (nums[i] > first) {
                three = second;
                second = first;
                first = nums[i];
            } else if (nums[i] > second) {
                three = second;
                second = nums[i];
            } else if (nums[i] > three) {
                three = nums[i];
            }
        }
        return first * second * three;
    }

    public static void main(String[] args) {
        int[] nums = new int[10];
        Random random = new Random();
        for (int i = 0; i < 10; i++) {
            testSort(nums, random);
        }
    }

    private static void testSort(int[] nums, Random random) {
        for (int i = 0; i < 10; i++) {
            nums[i] = random.nextInt(100);
            System.out.print(nums[i] + " ");
        }
        System.out.println();
        customSort(nums,0,9);
        for (int i = 0; i < 10; i++) {
            System.out.print(nums[i] + " ");
        }
        System.out.println("\n-----------------------");
    }

    public static int maximumProduct2(int[] nums) {
        customSort(nums,0,nums.length-1);

        return 0;
    }

    private static void customSort(int[] nums, int start, int end) {
        if (end  > start) {
            int tag = quickSort(nums, start, end);
            customSort(nums, start, tag - 1);
            customSort(nums, tag + 1, end);
        }
    }

    private static int quickSort(int[] nums, int start, int end) {
        int right = end, left = start;
        int tagNum = nums[start];
        while (left < right) {
            while (nums[right] >= tagNum && right > left) right--;
            nums[left++] = nums[right];
            while (nums[left] < tagNum && right > left) left++;
            nums[right--] = nums[left];
        }
        nums[left] = tagNum;
        return left;
    }
}
